package leetcode.D600.T503;

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    /* 一刷
    public int[] nextGreaterElements(int[] nums) {
        int[] result = new int[nums.length];
        Deque<Integer> dq = new LinkedList<>();
        for(int j=0; j<2; ++j) {
            for(int i=nums.length-1; i>=0; --i) {
                while(!dq.isEmpty() && dq.getLast() <= nums[i]) {
                    dq.removeLast();
                }
                result[i] = dq.isEmpty() ? -1 : dq.getLast();
                dq.addLast(nums[i]);
            }
        }
        return result;
    }*/

    // 二刷
//    public int[] nextGreaterElements(int[] nums) {
//        int[] result = new int[nums.length];
//        Deque<Integer> dq = new LinkedList<>();
//        for(int n=0; n<2; ++n) {
//            for(int i=nums.length-1; i >= 0; --i) {
//                while(!dq.isEmpty() && dq.getLast() <= nums[i]) {
//                    dq.removeLast();
//                }
//                result[i] = dq.isEmpty() ? -1 : dq.getLast();
//                dq.addLast(nums[i]);
//            }
//        }
//        return result;
//    }

    // 三刷
    /*public int[] nextGreaterElements(int[] nums) {
        int[] result = new int[nums.length];
        Deque<Integer> dq = new LinkedList<>();
        for(int n=0; n<2; ++n) {
            for(int i=nums.length-1; i>=0; --i) {
                while(!dq.isEmpty() && nums[i] >= nums[dq.getFirst()]) {
                    dq.removeFirst();
                }
                result[i] = dq.isEmpty() ? -1 : nums[dq.getFirst()];
                dq.addFirst(i);
            }
        }
        return result;
    }*/

    // 三刷
    public int[] nextGreaterElements(int[] nums) {
        int[] result = new int[nums.length];
        Deque<Integer> dq = new LinkedList<>();
        for(int n=0; n<2; ++n) {
            for(int i=nums.length-1; i>=0; --i) {
                while(!dq.isEmpty() && dq.getLast() <= nums[i]) {
                    dq.removeLast();
                }
                result[i] = dq.isEmpty() ? -1 : dq.getLast();
                dq.addLast(nums[i]);
            }
        }
        return result;
    }
}
